// 思路： 希尔排序是插入排序的改进版，将数组分成若干个子数组，每个子数组进行插入排序
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 稳定性：不稳定
// 适用场景：数据量较小
// 不适用于数据量较大的情况
function shellSort(arr) {
    let gap = Math.floor(arr.length / 2)
    while(gap > 0) {
        for(let i = gap; i < arr.length; i++) {
            let temp = arr[i]
            let j = i
            while(j - gap >= 0 && arr[j - gap] > temp) {
                arr[j] = arr[j - gap]
                j -= gap
            }
            arr[j] = temp
        }
        gap = Math.floor(gap / 2)
    }
    return arr
}

const arr = [5, 3, 8, 4, 2];
console.log(shellSort(arr));